Samuel biết rằng quân đội Đông La Mã sẽ phải tiến vào đất nước của ông bằng cách vượt qua một loạt các con đèo hiểm trở và như vậy đây là cách để ngăn bước tiến của kẻ thù. Người Bulgaria đã xây dựng những con hào và mương dọc theo biên giới và tăng cường phòng thủ ở nhiều thung lũng bằng các bức tường và tháp canh, đặc biệt là ở Kleidion trên bờ sông Struma, nơi mà Basil sẽ cần phải vượt qua để đến được miền trung của Bulgaria. Samuel tăng cường củng cố phòng bị bên sườn phía bắc của núi Belasitsa, và các tiền đồn ở phía nam và phía đông của lâu đài Strumitsa.[10] Ioannes Scylitzes, một thung lũng lớn dọc sông Strumitsa là một nơi thuận lợi cho việc tấn công và được quân Đông La Mã chọn làm nơi quyết đấu nhiều năm trước đây, nay được một đội quân Bulgaria tinh nhuệ đóng giữ. Ngoài ra, Samuel chọn Strumitsa làm nơi đặt phòng tuyến của mình bởi nó nằm trên con đường từ Thessaloniki dẫn đến Thrace ở phía đông và Ohrid ở phía tây,[11] địa hình gồ ghề ở phía nam đã được kết hợp với các hàng rào cọc nhọn và những bức tường chắc chắn được chốt giữ bởi các đơn vị tinh nhuệ nhất của Bugaria.[12]

Samuel quyết định đối mặt với Basileios II và quân đội của ông ta tại Kleidion không chỉ vì muốn gỡ gạc cho các thất bại liên tiếp, mà còn bởi mối lo âu về quyền lực của mình trong mắt của giới quý tộc, vốn bị lung lay bởi các chiến dịch của Basileios II. Năm 1005, ví dụ, thống đốc của cảng Dyrrhachium quan trọng ở Adriatic đã đầu hàng và dâng hai tay thành phố này cho Basileios II [13] Để đối mặt với mối đe dọa này, Samuel tập hợp một đội quân lớn để đối mặt với Đông La Mã, theo một số tài liệu con số này là 45.000 quân.[Ghi chú 1] Basileios II cũng đã chuẩn bị cẩn thận, trưng tập một đội quân lớn của riêng mình, trong đó bao hàm một số tướng lĩnh kinh nghiệm nhất của đế quốc như tổng đốc Philippopolis (hiện nay là thành phố Plovdiv), Xiphias Nikephorros, người đã chinh phục thủ đô Bulgaria cũ Pliska và Preslav từ Samuel trong năm 1001.